// 73. 矩阵置零
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        vector<int>row(m),col(n);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(!matrix[i][j]){
                    row[i]=col[j]=true;//标记
                }
            }
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(row[i]||col[j]){
                    matrix[i][j]=0;
                }
            }
        }
    }
};


// 54. 螺旋矩阵
class Solution {
    // 在全局作用域中定义一个静态编译时常量
    static constexpr int direction[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if(matrix.size()==0||matrix[0].size()==0){
            return{};
        }

        int rows=matrix.size(),columns=matrix[0].size();
        vector<vector<bool>>visited(rows,vector<bool>(columns));
        int total=rows*columns;
        vector<int>order(total);

        int row=0,col=0;
        int directionIndex=0;
        for(int i=0;i<total;i++){
            order[i]=matrix[row][col];
            visited[row][col]=true;
            //next用于判断
            int nextRow=row+direction[directionIndex][0],nextCol=col+direction[directionIndex][1];
            if(nextRow<0||nextRow>=rows||nextCol<0||nextCol>=columns||visited[nextRow][nextCol]){
                directionIndex=(directionIndex+1)%4;//切换方向
            }
            row+=direction[directionIndex][0];
            col+=direction[directionIndex][1];
            //二者为整体方向的一个进位
        }
        return order;
    }
    
};

//48. 旋转图像
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        //拷贝matrix->tmp;（在写入一个元素matrix[i][j]→matrix[j][n−1−i]后，原矩阵元素matrix[j][n−1−i]就会被覆盖（即丢失），而此丢失的元素就无法被写入到旋转后的索引位置了。）
        vector<vector<int>>tmp=matrix;
        //根据矩阵顺时针九十度旋转前后的元素位置映射公式：
        //matrix[i][j]->matrix[j][n-1-i];
         for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[j][n - 1 - i] = tmp[i][j];
            }
        }

    }
};


//240. 搜索二维矩阵 II
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int i=matrix.size()-1,j=0;//左下角坐标
        while(i>=0&&j<matrix[0].size())//到右上角的范围
        {
            if(matrix[i][j]>target) i--;
            else if(matrix[i][j]<target) j++;
            else return true;
        }
        return false;
        
    }
};


//